package com.leetcode.链表.合并链表;

import com.leetcode.公共.ListNode;

/**
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 */
public class 合并两个有序链表 {
    public static void main(String[] args) {

    }

    /**
     * 常规写法 迭代
     *
     * @param k1
     * @param k2
     * @return
     */
    public ListNode mergeTwoLists(ListNode k1, ListNode k2) {
        if (k1 == null) return k2;
        if (k2 == null) return k1;

        ListNode head;
        if (k1.val <= k2.val) {
            head = k1;
            k1 = k1.next;
        } else {
            head = k2;
            k2 = k2.next;
        }

        ListNode cur = head;
        while (k1 != null && k2 != null) {
            if (k1.val <= k2.val) {
                cur = cur.next = k1;
                k1 = k1.next;
            } else {
                cur = cur.next = k2;
                k2 = k2.next;
            }
        }

        if (k1 == null) {
            cur.next = k2;
        } else {
            cur.next = k1;
        }
        return head;
    }

    /**
     * 使用虚拟头节点的常规写法 迭代
     *
     * @param k1
     * @param k2
     * @return
     */
    public ListNode mergeTwoLists2(ListNode k1, ListNode k2) {
        if (k1 == null) return k2;
        if (k2 == null) return k1;
        // 首元节点
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (k1 != null && k2 != null) {
            if (k1.val <= k2.val) {
                cur = cur.next = k1;
                k1 = k1.next;
            } else {
                cur = cur.next = k2;
                k2 = k2.next;
            }
        }

        if (k1 == null) {
            cur.next = k2;
        } else {
            cur.next = k1;
        }
        return head.next;
    }

    /**
     * 递归解决
     *
     * @param k1
     * @param k2
     * @return
     */
    public ListNode mergeTwoLists3(ListNode k1, ListNode k2) {
        if (k1 == null) return k2;
        if (k2 == null) return k1;

        if (k1.val <= k2.val) {
            k1.next = mergeTwoLists3(k1.next, k2);
            return k1;
        } else {
            k2.next = mergeTwoLists3(k1, k2.next);
            return k2;
        }
    }
}
